Kể từ khi phát hành, "Paparazzi" đã nhận được những phản hồi tích cực từ giới phê bình âm nhạc. Năm 2011, tạp chí Rolling Stone đã gọi bài hát là bài hát xuất sắc thứ hai mọi thời đại của nữ ca sĩ, dành lời khen ngợi cho chủ đề và phần nhạc nền của nó.[18] Nhà phê bình Jill Menze từ tạp chí Billboard đã tán dương chất giọng của Lady Gaga trong ca khúc qua dòng nhận xét: "Bản ballad đầy ắp sự ám ảnh danh vọng 'Paparazzi' đã cho mọi người thấy được sự thông thạo của Gaga thông qua những quãng âm trong giọng hát của cô."[19] Alexis Petridis đến từ báo The Guardian đã nhận xét về bài hát như sau: "Bạn có thể sẽ cảm thấy chán nản khi phải nghe chủ đề chính của album phải lặp đi lặp lại liên tục, nhưng chính cái giai điệu của 'Paparazzi' đã chiếm lấy một phần não bộ của bạn và làm cho nó không thể thay đổi ý định."[20] Stephen Thomas Erlewine từ trang web AllMusic đã miêu tả bài hát là tài tình và cho rằng nó "vừa là một bản nhạc pop dở tệ nhưng lộng lẫy vừa là một bản parody có chất lượng tuyệt hảo của bản nhạc pop ấy."[21]

Fraser McAlpine từ đài BBC đã gọi "Paparazzi" là "một trong những câu chuyện đáng sợ có sức hút thần kỳ của nhạc pop, trong đó Gaga có sử dụng phép ẩn dụ và đã kể cho chúng ta nghe câu chuyện về người cô thích thầm rồi từ đó nêu cho chúng ta biết về quá trình tìm kiếm sự nổi tiếng."[22] David Balls từ Digital Spy đã dành lời khen cho Lady Gaga khi quyết định cho ra mắt một bài hát vừa phải sau khi ra mắt hai bản có tiết tấu nhanh ("Just Dance" và "Poker Face"), cho rằng "nhờ vào phần điệp khúc dễ bắt vào lòng người và những lời ca khéo léo và mang chủ đề người nổi tiếng, [...] được hỗ trợ bởi một video âm nhạc đam mê lạc thú, có vẻ rằng Gaga vẫn đang cai trị toàn bộ chúng ta."[23]

Evan Sawdey từ tạp chí trực tuyến PopMatters đã nhận thấy rằng cả hai đĩa đơn "Paparazzi" và "Poker Face" mang phong cách âm nhạc giống với "Just Dance" nhưng cho rằng "không bao giờ cảm thấy như Gaga đang cố tình lặp lại như vậy".[11] Freedom du Lac của nhật báo The Washington Post đã nhận xét rằng dù Gaga đã trở nên khá đàng hoàng trong khi ngân ca "Paparazzi" như đang phản đối một điều gì đó, nhưng bài hát lại thành ra không được truyền cảm, không có cá tính và nhạt nhẽo.[24] Erika Howard từ tờ New Times Broward-Palm Beach đã gọi "Paparazzi" là bài hát gây ấn tượng mạnh nhất trong album.[17]

Jon Caramanica đến từ nhật báo The New York Times viết rằng "Paparazzi" là một bức thư tình từ cánh nhiếp ảnh gia dành cho đối tượng được chụp, tuy nhiên lại không đề cập gì mấy đến chuyện tình cảm ấy có đến từ hai phía hay không. Nhà phê bình cũng cho rằng Lady Gaga đang phác họa ra một hành động liều lĩnh của cô trên trang giấy viết nhạc và đang ngang ngạnh phô trương ra tính hồn nhiên của mình mà không hề giễu cợt người khác quá đáng."[25] Pitchfork Media đã liệt "Paparazzi" vào vị trí thứ 83 trong danh sách 100 bài hát hay nhất năm 2009.[26] NME đã xếp ca khúc tại vị trí thứ 9 trong danh sách những bài hát hay nhất năm 2009.[27]